package 二叉树.树基本知识与重建;

/**
 * Created by Administrator on 2017/8/5.
 */
//题目：
//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
//        假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
//        例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
//        则重建二叉树并返回。

//画图重建二叉树：
//1、前序遍历：根、左、右；
//2、中序遍历：左、根、右； //发现左中节点数加起来一样多
//3、后序遍历：左，右，根；
// 1是根，所以4/7/2是树的左节点，5/3/8/6是树的右节点
    // 4/7/2对应前序遍历的2/4/7(前序遍历的第一个节点是根，所以，在中序遍历中认定4/7是根2的左子树，剩余的类推)

public class ReConstructBinaryTree {
    //测试主方法：
    public static void main(String[] args) {
        int[] pre={1,2,4,7,3,5,6,8};
        int[] in={4,7,2,1,5,3,8,6};
        //返回网友构建的二叉树
        //我重新写的
        TreeNode treeNode1 = new ReConstructBinaryTree().creatBinaryByPreAndInPrint(pre, in);
        //原版：
        TreeNode treeNode2 = new ReConstructBinaryTree().reConstructBinaryTree(pre, in);
        TreeNodeTest.preorderTraversal(treeNode1);
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        //-------------------------------------------------
        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
//    递归思想，每次将左右两颗子树当成新的子树进行处理，中序的左右子树索引很好找，
//    前序的开始、结束索引通过计算中序中左、右子树的大小来计算，
//    然后递归求解，直到startPre>endPre||startIn>endIn说明子树整理完到。方法每次返回左子树和右子树的根节点
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {

        if(startPre>endPre||startIn>endIn) //说明字树整理完毕
            return null;
        TreeNode root=new TreeNode(pre[startPre]); //每颗子树的根节点肯定是pre子数组的首元素，所以每次新建一个子树的根节点

        for(int i=startIn;i<=endIn;i++)//遍历中序二叉树
            if(in[i]==pre[startPre]){ //因为元素不重复，故可以用中序来区分原始树的左右孩子(中序节点和前序首节点一样，即中间节点，可以自己画树)
                //原树节点确定原理：
                //
                //中序in的左右孩子已经找到，即以in中索引i为分界点，故中序一次整理的范围为[startIn,i-1]
                //前序pre的一次整理范围很容易知道为[startPre+1,?]，按照不管中序还是前序，
                    // 原树左右孩子节点个数一样(即这里字数组的长度都是一样的)，故前序右节点为：
                    //startPre+1+[(i-1)-startIn] = startPre+i-startIn
                root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                //同上分析：前序pre的一次整理范围很容易知道为[?,endPre]，?需要计算中序字树的大小：
                //?= endPre- [endIn-(i+1)] = i-startIn+startPre+1
            }

        return root;
    }
    //-------------------------------------------------------------------
    //我的重写1：
    public TreeNode creatBinaryByPreAndInPrint(int[] pre,int[] in){
        TreeNode root=creatBinaryByPreAndInPrint(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    public TreeNode creatBinaryByPreAndInPrint(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){
        if(startPre>endPre||startIn>endIn) return null; //即已经将数组搜索完
        TreeNode root=new TreeNode(pre[startPre]);//中序遍历的首元素即原始树的中间根节点

        //遍历前序数组，找到原始树的中间节点
        for (int i = startIn; i <=endIn ; i++) {
            if(in[i]==pre[startPre]){
                //一个原则：根+左子树节点数 = 左字树节点数+根
                root.left=creatBinaryByPreAndInPrint(pre,startPre+1,startPre+1+((i-1)-startIn),
                        in,startIn,i-1); //设定区间的时候去掉中间节点(即startPre和i)
                root.right=creatBinaryByPreAndInPrint(pre,endPre-(endIn-(i+1)),endPre,
                        in,i+1,endIn);
            }
        }
        return root;//返回根节点
    }


    //-------------------------------------------------------------------
    //我的重写2：
    public TreeNode reConstructBinaryTree2(int [] pre,int [] in) {
        TreeNode treeNode=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return treeNode;
    }
    public TreeNode reConstructBinaryTree2(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd){
        //遍历完子树
        if(preStart>preEnd||inStart>inEnd) return null;
        //建立根节点(根节点即前序遍历的第一个)
        TreeNode root=new TreeNode(pre[preStart]);
        //在中序遍历中寻找根节点，用来区分出左右子树
        for(int i=inStart;i<=inEnd;i++){
            if(in[i]==pre[preStart]){//中序左右子树索引范围很好确定，前序只能得到一个界限，另一个要根据一个原则计算：根+左子树节点数 = 左字树节点数+根
                //左子树(因为子树中要跟新根，所以注意要剔除现在的根：前序中现在根索引为preStart,中序中现在根索引为i)
                root.left=reConstructBinaryTree(pre,preStart+1,preStart+1+((i-1)-inStart),
                                                in,inStart,i-1);
                //右子树
                root.right=reConstructBinaryTree(pre,preEnd-(inEnd-(i+1)),preEnd,
                                                 in,i+1,inEnd);
            }
        }
        return root;
    }
}
